package com.algorithm.offer.tree;

import java.util.Stack;

/**
 * @Author: huangzhigao
 * @Date: 2021/11/15 21:55
 * <p>
 * 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1
 */
public class JZ55 {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return TreeDepth(root.left) > TreeDepth(root.right) ? TreeDepth(root.left) + 1 : TreeDepth(root.right) + 1;
    }


    public String ReverseSentence(String str) {
        if(str == null || str.length() == 0){
            return str;
        }
        StringBuilder stringBuilder = new StringBuilder();
        Stack stack = new Stack();
        char[] chars = str.toCharArray();
        for(int i = chars.length-1;i>-1;i--){
            if(chars[i]!=' '){
                stack.push(chars[i]);
            }else {
                while (!stack.isEmpty()){
                    stringBuilder.append(stack.pop());
                }
                stringBuilder.append(" ");
            }
        }
        while (!stack.isEmpty()){
            stringBuilder.append(stack.pop());
        }
        return stringBuilder.toString();



    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
